package dp.test188;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/7/23 11:38
 */
public class Solution2 {

    public int maxProfit(int k, int[] prices) {
        if(prices == null || prices.length == 0 || k == 0) return 0;
        int n = prices.length;
        int[][] dp = new int[n][k + 1];
        for(int len = 1; len <= k; len++){
            for(int c = 1; c < n; c++){
                int min = Integer.MAX_VALUE;
                for(int p = 0; p < c; p++){
                    min = Math.min(min, prices[p] - dp[p][len - 1]);
                }
                dp[c][len] = Math.max(dp[c - 1][len], prices[c] - min);
            }
        }
        return dp[n - 1][k];
    }

    // 优化
    public int maxProfit2(int k, int[] prices) {
        if(prices == null || prices.length == 0 || k == 0) return 0;
        int[] dp = new int[k + 1];
        int min[] = new int[k + 1];
        for (int i = 1; i <= k; i++) {
            min[i] = prices[0];
        }
        for (int i = 1; i < prices.length; i++) {
            for (int j = 1; j <= k; j++) {
                min[j] = Math.min(prices[i] - dp[j - 1], min[j]);   // 每次更新的时候，记录上一轮的最小值
                dp[j] = Math.max(dp[j], prices[i] - min[j]);
            }
        }
        return dp[k];
    }
}
